package 题组;

/**
 * @author 挚爱之夕
 * @date 2021/9/7 - 09 - 07 - 19:53
 * @Description: 题组
 * @Version: 1.0
 */
public class _002_最大子序列和 {
    public static void main(String[] args) {
        int[] a = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        int answer = maxSubArray(a);
        System.out.println(answer);
        answer = maxSubArray1(a);
        System.out.println(answer);
    }
    /**
     * 递推法(O(N))
     * 记录出现的连续累加最大值
     * 如果前面累计和出现负数，则舍弃，从当前数与后面进行累加
     */
    private static int maxSubArray(int[] nums) {
        int max = nums[0];
        int maxOfI = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(maxOfI>0){
                maxOfI+=nums[i];
            }else{
                maxOfI = nums[i];
            }
            if(maxOfI>max){
                max = maxOfI;
            }
        }
        return max;
    }
    //动规:考虑加上当前元素与当前元素比，是否更大。如果更大则加上继续累加，否则从当前元素开始累加
    private static int maxSubArray1(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}
